package com.fh.twopointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和
 * @author fuhao
 * @date 2025/10/14 22:18
 */
public class T18FourSum {

    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new ArrayList<>();
            int n = nums.length;
            if (nums == null || n < 4) {
                return result;
            }
            // 1. 排序
            Arrays.sort(nums);

            for (int i = 0; i < n - 3; i++) {
                // 对第一个数去重
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 剪枝：当前最小值已大于target，后面只会更大，直接跳出
                if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                    break;
                }
                // 剪枝：当前最大值仍小于target，需要增大第一个数
                if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }

                for (int j = i + 1; j < n - 2; j++) {
                    // 对第二个数去重
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
                        continue;
                    }
                    // 剪枝：当前两个数确定后，最小值已大于target
                    if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                        break;
                    }
                    // 剪枝：当前两个数确定后，最大值仍小于target
                    if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                        continue;
                    }

                    int left = j + 1;
                    int right = n - 1;
                    while (left < right) {
                        // 使用long防止整数溢出
                        long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                        if (sum == target) {
                            result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            // 对双指针去重
                            while (left < right && nums[left] == nums[left + 1]) {
                                left++;
                            }
                            while (left < right && nums[right] == nums[right - 1]) {
                                right--;
                            }
                            // 找到答案后，双指针同时移动继续寻找
                            left++;
                            right--;
                        } else if (sum < target) {
                            left++;
                        } else {
                            right--;
                        }
                    }
                }
            }
            return result;
        }
    }
}
